/**
 * 比较经典的一道 dp 问题
 * dp[i] 记录的是下标索引 i 的前面比其小的数的个数和自己的总和（）
 */
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
  int lengthOfLIS(vector<int> &nums) {
    int len = nums.size();
    int maxLen = 1;
    vector<int> dp(len, 1);
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = max(dp[i], dp[j] + 1);
          maxLen = max(maxLen, dp[i]);
        }
      }
    }
    return maxLen;
  }
};
